package com.cwj;

public class Trie {

    Trie[] son = new Trie[26];
    int cnt = 0;
    boolean isLeaf;


    public void add(String s) {
        Trie trie = this;
        char[] cs = s.toCharArray();
        for (int i = 0; i < cs.length; i++) {
            if (trie.son[cs[i] - 'a'] == null) {
                trie.son[cs[i] - 'a'] = new Trie();
            }
            trie = trie.son[cs[i] - 'a'];
            trie.cnt++;
            trie.isLeaf = true;
        }
    }

    public int contains(String s) {
        Trie trie = this;
        int ans = 0;
        char[] cs = s.toCharArray();
        for (int i = 0; i < cs.length; i++) {
            if (trie.son[cs[i] - 'a'] == null) {
                return ans;
            }
            trie = trie.son[cs[i] - 'a'];
            ans += trie.cnt;
        }
        return ans;
    }
}
